package 常见经典递归过程解析;

import java.util.HashSet;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 字符串的全部子序列
// 子序列本身是可以有重复的，只是这个题目要求去重
// 测试链接 : https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a
public class Code01_Subsequences {

    public String[] generatePermutation1 (String s) {
        char[] strChar = s.toCharArray();
        // 使用hashset去重
        HashSet<String> set = new HashSet<>();
        f1(strChar, 0, new StringBuilder(), set);
        String[] strs = new String[set.size()];
        int i = 0;
        for (String string : set) {
            strs[i++] = string;
        }
        return strs;
    }

    // s[i...]，之前决定的路径path，set收集结果时去重
    public static void f1(char[] s, int i, StringBuilder path, HashSet<String> set){
        if(i == s.length){
            set.add(path.toString());
        }else {
            // 加到路径中去
            path.append(s[i]);
            f1(s, i+1, path, set);
            // 从路径中移除，恢复现场
            path.deleteCharAt(path.length() - 1);
            f1(s, i+1, path, set);
        }
    }

    public String[] generatePermutation (String s) {
        char[] strChar = s.toCharArray();
        HashSet<String> set = new HashSet<>();
        f(strChar, 0, new char[strChar.length], 0, set);
        String[] ans = new String[set.size()];
        int i = 0;
        for (String string : set) {
            ans[i++] = string;
        }
        return ans;
    }

    // path使用变量 size 来控制 数的个数
    public static void f(char[] s, int index, char[] path, int size, HashSet<String> set){
        if(index == s.length){
            set.add(String.valueOf(path, 0, size));
        }else {
            path[size] = s[index];
            f(s, index+1, path, size+1, set);
            f(s, index+1, path, size, set);
        }
    }
}
